package leetcode.binaryTree;

import utils.printer.BinaryTrees;
import datastructure.tree.BinarySearchTree;
import datastructure.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: https://leetcode.cn/problems/maximum-width-of-binary-tree/
 * 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
 *
 * 树的 最大宽度 是所有层中最大的 宽度 。
 *
 * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
 *
 * 题目数据保证答案将会在 32 位 带符号整数范围内。
 *
 * 草稿(旧) 3
 *
 * @Author Ammar
 * @Create 2023/3/30 16:41
 */
public class _662_二叉树最大宽度 {

    public static int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        // 中序遍历给所有的节点编号，每层用编号最大的节点的编号减编号最小的节点的编号 + 1 就是当前层的宽度，求出最大的宽度
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1); // 添加初始编号 1
        int width = 1; // 初始宽度
        while (queue.size() != 0) {
            int size = queue.size();
            // 层序遍历
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 去除保存的节点编号
                Integer index = linkedList.removeFirst();
                if (node.left != null) {
                    // 存入下一层的左子树编号
                    linkedList.add(index * 2);
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    // 存入下一层的右子树编号
                    linkedList.add(index * 2 + 1);
                    queue.offer(node.right);
                }
            }
            // 计算当前层的宽度，如果宽度大于上一层的宽度，就覆盖 width
            if (linkedList.size() != 0 && width < linkedList.getLast() - linkedList.getFirst() + 1) {
                width = linkedList.getLast() - linkedList.getFirst() + 1;
            }
        }
        return width;
    }

    public static void main(String[] args) {
        Integer[] data = new Integer[]{
                7, 4, 9, 2, 5, 8 ,11, 3, 12, 1
        };
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            binarySearchTree.add(data[i]);
        }
        BinaryTrees.print(binarySearchTree);
        System.out.println(widthOfBinaryTree(binarySearchTree.getRoot()));
    }
}
